#include "ArbolBMas.h"

ArbolBMas::ArbolBMas(string ruta_archivo, unsigned int M){
	this->primeraHoja = 0;
	this->path_file = ruta_archivo;
	this->block_Size = M*64;
	inicializar_archivos_de_bloques(ruta_archivo);
	this->control_Data_Size= TAM_CONTROL_NODO;
	this->raiz = obtener_Nodo_desde_Bloque(0);

	if (this->raiz){
		this->contador_de_nodos=this->lector_Nodos->obtener_tamanio_Archivo()/this->block_Size;
	}
	else{
		inicializar_raiz();
	}

}

void ArbolBMas::inicializar_archivos_de_bloques(string ruta){
	string rutaAux = ruta + "_Nodos.txt";
	this->lector_Nodos = new LectorDeNodos(rutaAux,this->block_Size);
	this->escritor_Nodos = new EscritorNodo(rutaAux,this->block_Size);
}

void ArbolBMas::inicializar_raiz(){
	this->raiz=obtener_Hoja();
	this->raiz->idNodo=this->primeraHoja = 0;
	(static_cast <Hoja*> (raiz))->hoja_siguiente = 0;
	this->contador_de_nodos = 1;
}

ArbolBMas::~ArbolBMas(){
	if	(raiz){
		liberar_Memoria_Nodo(raiz);
	}
	delete this->escritor_Nodos;
	delete this->lector_Nodos;

}

Hoja* ArbolBMas::obtener_Hoja(){
	Hoja* hoja = new Hoja(this->block_Size);
	return hoja;
}

Interno* ArbolBMas::obtener_Nodo_Interno(int level){
	Interno* interno = new Interno(level,this->block_Size);
	return interno;
}

int ArbolBMas::insertar_en_hoja(Hoja* nodo_actual, Registro* registro){

	quitar_FrontCoding_Hoja(&nodo_actual);
	int i = nodo_actual->contador_claves-1;
	while (i >= 0 && registro->getClave()->getClave() < nodo_actual->claves[i].getClave()){
		nodo_actual->claves[i+1]=nodo_actual->claves[i];
		nodo_actual->registro[i+1]=nodo_actual->registro[i];
		i--;
	}

	nodo_actual->registro[i+1]=*registro;
	nodo_actual->claves[i+1]=*registro->getClave();
	nodo_actual->contador_claves++;

	if (nodo_actual->contador_claves > 1){
		aplicar_FrontCoding_Hoja(&nodo_actual);
	}
	nodo_actual->espacioOcupado += nodo_actual->registro[i+1].getTamanio() + registro->getClave()->getTamanio() + TAM_CONTROL_REGISTRO;

		if (nodo_actual->isOverflow(block_Size-control_Data_Size)){
			return SOBREFLUJO;
		}
		else return EXIT_SUCCESS;
}


bool ArbolBMas::insertar(Registro* registro){
	Nodo* hijo_auxiliar = NULL;
	Clave clave_raiz_aux;

	bool resultado = insertar_Recursivo(raiz, registro, &clave_raiz_aux, &hijo_auxiliar);

	if (hijo_auxiliar){
		guardar_Nodo_en_Bloque(hijo_auxiliar);
		Interno *nueva_raiz = obtener_Nodo_Interno(raiz->nivel + 1);

		raiz->idNodo = obtener_IdNodo();
		if (this->raiz->isNodoHoja()) {
			this->primeraHoja = this->raiz->idNodo;
		}

		guardar_Nodo_en_Bloque(raiz);

		nueva_raiz->claves[0] = clave_raiz_aux;
		nueva_raiz->hijos[0] = raiz->idNodo;
		nueva_raiz->hijos[1] = hijo_auxiliar->idNodo;
		nueva_raiz->contador_claves = 1;
		nueva_raiz->espacioOcupado += clave_raiz_aux.getTamanio() + TAM_CONTROL_REGISTRO;
		nueva_raiz->idNodo = 0;
		guardar_Nodo_en_Bloque(nueva_raiz);

		liberar_Memoria_Nodo(raiz);
		liberar_Memoria_Nodo(hijo_auxiliar);

		raiz = nueva_raiz;
	}
	return resultado;
}

bool ArbolBMas::insertar_Recursivo(Nodo* nodo_actual, Registro* registro, Clave* new_key_root, Nodo** new_node){

	if (nodo_actual->isNodoHoja()){
		Hoja *hoja_actual = static_cast<Hoja*> (nodo_actual);
		int posicion = obtener_Posicion_Insercion(hoja_actual, *registro->getClave());
		int resultado_operacion=insertar_en_hoja(hoja_actual,registro);

		if (resultado_operacion==1){

				split_Hoja(hoja_actual, new_key_root, new_node);
				aplicar_FrontCoding_Hoja(&hoja_actual);
				aplicar_FrontCoding(&(*new_node));

				if (posicion >= hoja_actual->contador_claves) {
					posicion -= hoja_actual->contador_claves;
					hoja_actual = static_cast<Hoja*> (*new_node);
				}
		}
		else{
				if (hoja_actual->nivel == 0){
						aplicar_FrontCoding_Hoja(&hoja_actual);
					}
				}
				if (new_node && hoja_actual != *new_node && posicion == hoja_actual->contador_claves - 1) {
					quitar_FrontCoding_Hoja(&hoja_actual);
					*new_key_root = *registro->getClave();
					aplicar_FrontCoding_Hoja(&hoja_actual);
				}
			return true;
	}else{

		Interno *interno_actual= static_cast<Interno*> (nodo_actual);
		Clave nueva_clave;
		Nodo* new_hijo = NULL;

		int posicion = obtener_Posicion_Insercion(interno_actual, *registro->getClave());
		Nodo* n_hijo = obtener_Nodo_desde_Bloque(interno_actual->hijos[posicion]);
		bool resultado = insertar_Recursivo(n_hijo, registro, &nueva_clave, &new_hijo);

		if (new_hijo) {

			interno_actual->espacioOcupado += (nueva_clave).getTamanio() + TAM_CONTROL_REGISTRO;

			if (interno_actual->isOverflow( block_Size-control_Data_Size)) {
				interno_actual->espacioOcupado -= (nueva_clave).getTamanio() + TAM_CONTROL_REGISTRO;
				split_Nodo_Interno(interno_actual, new_key_root, new_node, posicion);

				if (posicion == interno_actual->contador_claves + 1
						&& interno_actual->contador_claves < (*new_node)->contador_claves) {

					Interno *nuevo_interno = static_cast<Interno*> (*new_node);
					interno_actual->claves[interno_actual->contador_claves] = *new_key_root;
					interno_actual->hijos[interno_actual->contador_claves + 1] = nuevo_interno->hijos[0];
					interno_actual->contador_claves++;
					interno_actual->espacioOcupado += (*new_key_root).getTamanio() + TAM_CONTROL_REGISTRO;
					nuevo_interno->hijos[0] = new_hijo->idNodo;
					*new_key_root = nueva_clave;

					guardar_Nodo_en_Bloque(new_hijo);
					liberar_Memoria_Nodo(new_hijo);

					guardar_Nodo_en_Bloque(n_hijo);
					liberar_Memoria_Nodo(n_hijo);
					return resultado;
				} else {
					if (posicion >= interno_actual->contador_claves + 1) {
						posicion -= (interno_actual->contador_claves + 1);
						interno_actual= static_cast<Interno*> (*new_node);
					}
				}
			}
			interno_actual->espacioOcupado -= (nueva_clave).getTamanio() + TAM_CONTROL_REGISTRO;
			int i = interno_actual->contador_claves;
			while (i > posicion) {
				interno_actual->claves[i] = interno_actual->claves[i - 1];
				interno_actual->hijos[i + 1] = interno_actual->hijos[i];
				i--;
			}
			interno_actual->claves[posicion] = nueva_clave;
			interno_actual->hijos[posicion + 1] = new_hijo->idNodo;
			interno_actual->contador_claves++;
			interno_actual->espacioOcupado += nueva_clave.getTamanio() + TAM_CONTROL_REGISTRO;

			guardar_Nodo_en_Bloque(new_hijo);
			liberar_Memoria_Nodo(new_hijo);
		}

		guardar_Nodo_en_Bloque(n_hijo);
		liberar_Memoria_Nodo(n_hijo);
		return resultado;

	}
}


void ArbolBMas::aplicar_FrontCoding_Hoja(Hoja** n_hoja){

    (*n_hoja)->espacioOcupado -= ((*n_hoja))->registro[0].getTamanio();
    (*n_hoja)->registro[0].sacarElFrontCoding(((*n_hoja))->registro[0].getClave()->getClave(), this->path_file);
    (*n_hoja)->espacioOcupado += (*n_hoja)->registro[0].getTamanio();
	string primera = (*n_hoja)->registro[0].getClave()->getClave();

	for (int i = 1; i < (*n_hoja)->contador_claves ; i++){
		string proxima = (*n_hoja)->registro[i].getClave()->getClave();
		(*n_hoja)->espacioOcupado -= ((*n_hoja))->registro[i].getTamanio();
		(*n_hoja)->registro[i].transformarAFrontCoding(primera, this->path_file);
		(*n_hoja)->espacioOcupado += ((*n_hoja))->registro[i].getTamanio();
		primera=proxima;
	}
}

void ArbolBMas::aplicar_FrontCoding(Nodo** nodo){

	static_cast<Hoja*>(*nodo)->espacioOcupado -= (static_cast<Hoja*>(*nodo))->registro[0].getTamanio();
	static_cast<Hoja*>(*nodo)->registro[0].sacarElFrontCoding((static_cast<Hoja*>(*nodo))->registro[0].getClave()->getClave(), this->path_file);
	static_cast<Hoja*>(*nodo)->espacioOcupado += static_cast<Hoja*>(*nodo)->registro[0].getTamanio();
	string primera = static_cast<Hoja*>(*nodo)->registro[0].getClave()->getClave();

	for (int i = 1; i < static_cast<Hoja*>(*nodo)->contador_claves ; i++){
		string proxima = static_cast<Hoja*>(*nodo)->registro[i].getClave()->getClave();
		static_cast<Hoja*>(*nodo)->espacioOcupado -= (static_cast<Hoja*>(*nodo))->registro[i].getTamanio();
		static_cast<Hoja*>(*nodo)->registro[i].transformarAFrontCoding(primera, this->path_file);
		static_cast<Hoja*>(*nodo)->espacioOcupado += (static_cast<Hoja*>(*nodo))->registro[i].getTamanio();
		primera=proxima;
	}
}

int ArbolBMas::	obtener_IdNodo(){

	int idNodo;
		this->contador_de_nodos++;
		idNodo = this->contador_de_nodos-1;
	return idNodo;
}

void ArbolBMas::guardar_Nodo_en_Bloque(Nodo* nodo){
	escritor_Nodos->ActualizarArchivoNodo(nodo, nodo->getNumero());
}

Nodo* ArbolBMas::obtener_Nodo_desde_Bloque(int id_nodo){
	Nodo * nodo = lector_Nodos->leer_Nodo(id_nodo);
	return nodo;
}

void ArbolBMas::liberar_Memoria_Nodo(Nodo* nodo){
	if (nodo->isNodoHoja()) {
		delete static_cast<Hoja*> (nodo);
	} else {
		delete static_cast<Interno*> (nodo);
	}
}

int ArbolBMas::obtener_Posicion_Insercion(Nodo *nodo, Clave clave) {

	if (nodo->contador_claves == 0)
		return 0;
	int inferior = 0;
	int superior = (nodo->contador_claves) - 1;

	while (inferior < superior) {
		int medio = (inferior + superior) / 2;
		if (clave.getClave() <= nodo->claves[medio].getClave()) {
			superior = medio - 1;
		} else {
			inferior = medio + 1;
		}
	}
	if (superior < 0 || (nodo->claves[superior].getClave() < clave.getClave()))
		superior++;

	return superior;
}

void ArbolBMas::split_Nodo_Interno(Interno* interno_actual, Clave* new_key_root, Nodo** new_interno, int nueva_posicion){

	int mitad = interno_actual->contador_claves / 2;

	if (nueva_posicion <= mitad && mitad > interno_actual->contador_claves - (mitad + 1)) {
		mitad--;
	}

	Interno *nuevo_interno_auxiliar = obtener_Nodo_Interno(interno_actual->nivel);
	nuevo_interno_auxiliar->idNodo = obtener_IdNodo();
	nuevo_interno_auxiliar->contador_claves = interno_actual->contador_claves - (mitad + 1);
	for (int posicion = mitad + 1; posicion < interno_actual->contador_claves; ++posicion) {
		int posicion_auxiliar = posicion - (mitad + 1);
		nuevo_interno_auxiliar->claves[posicion_auxiliar] = interno_actual->claves[posicion];
		nuevo_interno_auxiliar->hijos[posicion_auxiliar] = interno_actual->hijos[posicion];
		nuevo_interno_auxiliar->espacioOcupado += interno_actual->claves[posicion].getTamanio() + TAM_CONTROL_REGISTRO;
	}
	nuevo_interno_auxiliar->hijos[nuevo_interno_auxiliar->contador_claves] = interno_actual->hijos[interno_actual->contador_claves];
	interno_actual->contador_claves = mitad;
	interno_actual->espacioOcupado -= nuevo_interno_auxiliar->espacioOcupado;
	*new_key_root = interno_actual->claves[mitad];
	*new_interno = nuevo_interno_auxiliar;
}


void ArbolBMas::split_Hoja(Hoja* n_hoja, Clave* clave_promovida, Nodo** nueva_hoja){

	quitar_FrontCoding_Hoja(&n_hoja);
	int mitad_en_bytes = (n_hoja->espacioOcupado) / 2;
	int bytes_hijo_izq = 0;
	int total_claves = 0;

	while (total_claves < n_hoja->contador_claves && bytes_hijo_izq < mitad_en_bytes){
		bytes_hijo_izq += n_hoja->registro[total_claves].getTamanio() + n_hoja->claves[total_claves].getTamanio() + TAM_CONTROL_REGISTRO;
		total_claves++;
		if (bytes_hijo_izq > (this->block_Size - this->control_Data_Size)) {
			total_claves--;
			bytes_hijo_izq -= (n_hoja->registro[total_claves].getTamanio() + n_hoja->claves[total_claves].getTamanio() + TAM_CONTROL_REGISTRO);
			break;
		}
	}

	Hoja *nueva_hoja_auxiliar = obtener_Hoja();
	nueva_hoja_auxiliar->idNodo = obtener_IdNodo();
	nueva_hoja_auxiliar->contador_claves = n_hoja->contador_claves - total_claves;
	nueva_hoja_auxiliar->espacioOcupado = n_hoja->espacioOcupado - bytes_hijo_izq;
	nueva_hoja_auxiliar->hoja_siguiente = n_hoja->hoja_siguiente;

	for (int posicion = total_claves; posicion < n_hoja->contador_claves; ++posicion) {
		int auxPosicion = posicion - total_claves;
		nueva_hoja_auxiliar->claves[auxPosicion] = n_hoja->claves[posicion];
		nueva_hoja_auxiliar->registro[auxPosicion] = n_hoja->registro[posicion];
	}

	n_hoja->espacioOcupado -= nueva_hoja_auxiliar->espacioOcupado;
	n_hoja->contador_claves = total_claves;
	n_hoja->hoja_siguiente = nueva_hoja_auxiliar->idNodo;
	*clave_promovida = n_hoja->claves[n_hoja->contador_claves-1];
	*nueva_hoja = nueva_hoja_auxiliar;
}


void ArbolBMas::quitar_FrontCoding_Nodo(Nodo ** nodo){

	static_cast<Hoja*>(*nodo)->espacioOcupado -= (static_cast<Hoja*>(*nodo))->registro[0].getTamanio();
	static_cast<Hoja*>(*nodo)->registro[0].sacarElFrontCoding((static_cast<Hoja*>(*nodo))->registro[0].getClave()->getClave(), this->path_file);
	static_cast<Hoja*>(*nodo)->espacioOcupado += static_cast<Hoja*>(*nodo)->registro[0].getTamanio();

	for (int i = 1; i < static_cast<Hoja*>(*nodo)->contador_claves ; i++){
		static_cast<Hoja*>(*nodo)->espacioOcupado -= (static_cast<Hoja*>(*nodo))->registro[i].getTamanio();
		static_cast<Hoja*>(*nodo)->registro[i].sacarElFrontCoding(static_cast<Hoja*>(*nodo)->registro[i].getClave()->getClave(), this->path_file);
		static_cast<Hoja*>(*nodo)->espacioOcupado += (static_cast<Hoja*>(*nodo))->registro[i].getTamanio();
	}
}

Registro* ArbolBMas::buscar(string clave){

	Clave termino= Clave(clave);
	Registro* buscado=buscar_Recursivo(termino,this->raiz);
	return buscado;

}

Registro* ArbolBMas::buscar_Recursivo(Clave termino, Nodo* nodo){
	bool encontrado=false;
	int i=0;

	if (nodo->isNodoHoja()){

		Nodo* nodo_auxiliar = obtener_Nodo_desde_Bloque(nodo->idNodo);
		Hoja* hoja_actual = static_cast<Hoja*>(nodo_auxiliar);

		quitar_FrontCoding_Hoja(&hoja_actual);
		int posicion = obtener_Posicion_Insercion(hoja_actual, termino);

		while (!encontrado && hoja_actual->registro[posicion+i].getClave()->igual(&termino) && ((posicion+i)< hoja_actual->contador_claves) ){
				if (hoja_actual->registro[posicion+i].getClave()->igual(&termino)){
					encontrado = true;
				}
				++i;
		}
		if (encontrado){
			Registro* auxiliar= new Registro(hoja_actual->registro[posicion+i-1].getClave(),hoja_actual->registro[posicion+i-1].getOffset());
			return auxiliar;
		}
		else {
			Registro* auxiliar= new Registro(hoja_actual->registro[posicion+i].getClave(),hoja_actual->registro[posicion+i].getOffset());
			return auxiliar;
		}
	}
	else {
		Interno *interno_actual= static_cast<Interno*> (nodo);

		int posicion = obtener_Posicion_Insercion(interno_actual, termino);
		Nodo* n_hijo = obtener_Nodo_desde_Bloque(interno_actual->hijos[posicion]);

		Registro* auxiliar = buscar_Recursivo(termino,n_hijo);
		return auxiliar;

	}

}


void ArbolBMas::quitar_FrontCoding_Hoja(Hoja ** nodo){

    (*nodo)->espacioOcupado -= ((*nodo))->registro[0].getTamanio();
    (*nodo)->registro[0].sacarElFrontCoding(((*nodo))->registro[0].getClave()->getClave(), this->path_file);
    (*nodo)->espacioOcupado += (*nodo)->registro[0].getTamanio();

	for (int i = 1; i < (*nodo)->contador_claves ; i++){
		(*nodo)->espacioOcupado -= ((*nodo))->registro[i].getTamanio();
		(*nodo)->registro[i].sacarElFrontCoding((*nodo)->registro[i].getClave()->getClave(), this->path_file);
		(*nodo)->espacioOcupado += ((*nodo))->registro[i].getTamanio();
	}
}


void ArbolBMas::MostrarArbol (){
	ofstream fo;
	string ruta = this->path_file + ".txt";
	fo.open(ruta.c_str(), ios_base::out);
	fo << ".|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|" << endl << endl;
	fo << "			            ARBOL B+ de "; fo << this->path_file << "                  " << endl << endl;
	fo << ".|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|.|" << endl << endl;
	if (raiz){
		fo << "					TAMANIO NODO:  " << this->block_Size << endl;
		fo << "					PRIMER HOJA:  " << primeraHoja << endl;
		fo << "____________________________________________________________________________" << endl << endl;
	}
	if (this->raiz){
		toString(this->raiz,1, fo);
	}
	fo.flush();
	fo.close();
}

void ArbolBMas::EscribirListadoOrdenado (){
	ofstream file_list;
	string ruta = this->path_file +"listado"+ ".txt";
	file_list.open(ruta.c_str(), ios_base::out);
	Nodo* nodo_total = obtener_Nodo_desde_Bloque(this->primeraHoja);

		toString_listado(nodo_total, file_list);

		liberar_Memoria_Nodo(nodo_total);
		file_list.flush();
		file_list.close();
}

void ArbolBMas::toString_listado(Nodo* nodo, ofstream& file_list){

	Hoja *hoja = static_cast<Hoja*> (nodo);
	quitar_FrontCoding_Hoja(&hoja);

	for (int i=0; i < hoja->contador_claves; i++){
		file_list << hoja->registro[i].getClave()->getClave() << endl;
	}
	if (hoja->hoja_siguiente != 0){
		Nodo* nodo_aux = obtener_Nodo_desde_Bloque(hoja->hoja_siguiente);
		toString_listado(nodo_aux, file_list);
	}

}

void ArbolBMas::toString(Nodo* nodoAmostrar, int tab, ofstream& fo){

	if(nodoAmostrar){
		if (nodoAmostrar->isNodoHoja()) {
			Hoja *nodo = static_cast<Hoja*> (nodoAmostrar);
			for(int i=0 ; i<tab ; i++) fo << "  ";
				fo   << "id:" << nodo->idNodo <<  "|" << nodo->nivel << "|" << nodo->contador_claves << "(" << nodo->hoja_siguiente << ")    ";

			for(int i=0 ; i<tab ; i++) fo << "";
			for (int posicion = 0; posicion < nodo->contador_claves; ++posicion){
				fo << "|";
				Clave clave = (*nodo->registro[posicion].getClave());
				fo << clave.getClave();
				fo << ",";
				fo << nodo->registro[posicion].getOffset();
				fo << ",";
				fo << nodo->registro[posicion].getZero();
				fo << "|";
			}
			fo << endl;
		} else {
			Interno *nodoInt= static_cast<Interno*> (nodoAmostrar);
			fo << endl;
			for(int i=0; i<tab ; i++)
				fo << " ";
			fo << "id:" << nodoInt->idNodo << "|" << nodoInt->nivel << "|" << nodoInt->contador_claves << " (";
			for (int posicion = 0; posicion <= nodoInt->contador_claves; ++posicion) {
				if (posicion < nodoInt->contador_claves) {
					Clave clave = nodoInt->claves[posicion];
					fo << clave.getClave();
					if (posicion == nodoInt->contador_claves-1){
						fo << ")" << endl;
					}else{
						fo << "," ;
					}
				}
			}
			int * hijos;
			Nodo *hijo;
			for (int posicion = 0; posicion <= nodoInt->contador_claves; ++posicion) {

				hijos = nodoInt->getHijos();
				hijo = obtener_Nodo_desde_Bloque(hijos[posicion]);
				toString(hijo, tab+2, fo);
				if (hijo)
					liberar_Memoria_Nodo(hijo);
			}
			fo << endl;
		}
	}
}
